package day190705;

/**
 * @author LI DUO
 * @version 1.0
 * @date 2019/7/5 上午 11:28
 * 395. 至少有K个重复字符的最长子串
 * https://leetcode-cn.com/problems/longest-substring-with-at-least-k-repeating-characters/
 */
public class LongestSubstring {

    /**
     *解题思路：递归拆分子串，分治。先统计出每个字符出现的频次，维护一对双指针，从首尾开始统计，从首尾往中间排除，
     * 如果出现次数小于k则不可能出现在最终子串中，排除并挪动指针，然后得到临时子串，依次从头遍历，一旦发现出现频次小于k的字符，
     * 以该字符为分割线，分别递归求其最大值返回。
     * @param s
     * @param k
     * @return
     */
    public int longestSubstring(String s, int k) {
        int length = s.length();
        if (k > length || length == 0) {
            return 0;
        }
        if (k < 2) {
            return length;
        }
        return count(s.toCharArray(), k , 0, length - 1);
    }

    private int count(char[] chars, int k, int left, int right) {
        if (right - left + 1 < k) {
            return 0;
        }
        int[] num = new int[26];
        //  统计出现频次
        for (int i = left; i <= right; i++) {
            num [chars[i] - 'a'] ++;
        }
        //  如果该字符出现频次小于k，则不可能出现在结果子串中
        //  分别排除，然后挪动两个指针
        while (right - left + 1 >= k && num[chars[left] - 'a'] < k) {
            left ++;
        }
        while (right - left + 1 >= k && num[chars[right] - 'a'] < k) {
            right --;
        }
        if (right - left + 1 < k) {
            return 0;
        }
        //  得到临时子串，再递归处理
        for (int i = left; i <= right; i++) {
            //  如果第i个不符合要求，切分成左右两段分别递归求得
            if (num[chars[i] - 'a'] < k) {
                return Math.max(count(chars, k, left, i - 1), count(chars, k, i + 1, right));
            }
        }
        return right - left + 1;
    }
}
